package com.hy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2024/4/21
 * Time:12:40
 */
public class Dijkstra {

    /**
     * 使用 Dijkstra 算法计算从源节点到所有其他节点的最短路径。
     *
     * @param d 存储从源节点到各节点的最短距离的数组
     * @param s 源节点的索引
     * @param list 邻接表，表示图的结构
     */
    public void dijkstra(int[] d, int s, List<int[]>[] list) {
        // 初始化距离数组，将所有节点到源节点的距离设为无穷大，源节点自身距离为0
        Arrays.fill(d, Integer.MAX_VALUE);
        d[s] = 0;

        // 使用优先队列（最小堆）来存储节点及其到源节点的距离
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {return a[0] - b[0];});
        pq.offer(new int[]{0, s}); // 将源节点及其距离0加入优先队列

        while(!pq.isEmpty()){
            // 从队列中取出当前距离源节点最近的节点
            int[] nums = pq.poll();
            int dist = nums[0]; // 节点到源节点的距离
            int index = nums[1]; // 节点的索引

            // 如果当前节点的距离大于已知的最短距离，则忽略该节点
            if(dist > d[index]) continue;

            // 遍历当前节点的所有邻居节点
            for(int[] next : list[index]){
                int b = next[0]; // 邻居节点的索引
                int w = next[1]; // 边的权重
                int nd = dist + w; // 从源节点经过当前节点到邻居节点的距离

                // 如果通过当前节点发现了一条更短的路径，则更新邻居节点的最短距离，并将邻居节点加入队列
                if(nd < d[b]){
                    d[b] = nd;
                    pq.offer(new int[]{nd, b});
                }
            }
        }
    }
}
